﻿#include "Generation/Content/Architect.h"

#include "Generation/Graph/AdGraph.h"
#include "Generation/Piecemeal/Rng.h"
#include "System/GameConfiguration.h"

int reflowCount;


void Architect::InitStage(FStage* _stage)
{
	this->stage = _stage;
	reachability = new FReachability(_stage);

	auto tiles = _stage->Tiles;
	//todo：解决这个问题
	for (int i = 0; i < tiles->Count(); i ++)
	{
		auto tile = tiles->Get(i);
		tile.architect = this;
	}
}

void Architect::Rebuild(int seed, int vertCount, int minDistance, int maxDistance)
{
	generatedTree.Empty();
	Rng::rng()->Seed = seed;
	auto tree = GenerateTree(vertCount, minDistance, maxDistance);

	reflowCount = 0;
	ReFlow(tree, minDistance, maxDistance);
}

TArray<FSpanTreeNode*> Architect::GenerateTree(int vertCount, int minDistance, int maxDistance)
{
	int failedCount = 0;
	TArray<FSpanTreeNode*> _generatedTree = TArray<FSpanTreeNode*>();
	while (failedCount < 50)
	{
		auto tree = TryGenerateTree(vertCount, minDistance, maxDistance);

		if (tree == TArray<FSpanTreeNode*>()) failedCount++;
		else
		{
			_generatedTree = tree;
			break;
		}
	}

	if (_generatedTree != TArray<FSpanTreeNode*>())
	{
		UE_LOG(LogTD, Error, TEXT("生成树成功，失败次数：%d"), failedCount);

		for (int i = 0; i < _generatedTree.Num(); i++)
		{
			auto targetTreeNode = _generatedTree[i];
			FString prt = "无";
			if (targetTreeNode->ParentContext != nullptr) prt = targetTreeNode->ParentContext->VertexName;
			// %s, %s
			UE_LOG(LogTD, Error, TEXT("(%s,%s) Weight:%d 深度：%d"),
			       *targetTreeNode->SelfContext->VertexName,
			       *prt,
			       _generatedTree[i]->Weight, _generatedTree[i]->Depth
			);
		}

		return _generatedTree;
	}
	else
	{
		UE_LOG(LogTD, Error, TEXT("生成树失败，失败次数：%d"), failedCount);
		return _generatedTree;
	}
}

TArray<FSpanTreeNode*> Architect::TryGenerateTree(int vertCount, int minDistance, int maxDistance)
{
	AdGraph* alg = new AdGraph(vertCount);
	for (int i = 0; i < vertCount; i++) // 初始化顶点
	{
		FString text = TEXT("V");
		text.Append(FString::FromInt(i));
		alg->SetIndex(i, text);
	}

	for (int i = 0; i < vertCount; i++) // 生成全连通图，距离随机
	{
		int startID = i + 1;
		for (int j = startID; j < vertCount; j++)
		{
			int doubleDistance = Rng::rng()->Range(minDistance, maxDistance); //双向距离
			alg->AddEdge(i, j, doubleDistance);
			alg->AddEdge(j, i, doubleDistance);
		}
	}

	auto tree = alg->MiniSpanTree();

	// 规则筛选
	// 所有节点的孩子数量不能超过四个（一个房间门数量最多四个）：这种情况必须重新生成树
	// 不能一字长蛇，即，根节点必须至少三个孩子，或者其他任一节点必须至少两个孩子：这种情况必须重新生成树
	// 找到根节点，根节点最远子节点不能超过4个：最深层级不能大于4。
	// 不符合上述描述，需要重新生成树结构。
	bool isLine = true;
	for (int i = 0; i < tree.Num(); ++i)
	{
		if (tree[i]->ChildCount() > 4) return TArray<FSpanTreeNode*>(); //所有节点的孩子数量不能超过四个（一个房间门数量最多四个）：这种情况必须重新生成树

		//Debug.LogError("Depth：" + tree[i].Depth);
		if (tree[i]->Depth > 4) return TArray<FSpanTreeNode*>(); //找到根节点，根节点最远子节点不能超过4个：最深层级不能大于4。

		if (tree[i]->IsRoot())
		{
			if (tree[i]->ChildCount() >= 3)
			{
				isLine = false;
			}
		}
		else
		{
			if (tree[i]->ChildCount() >= 2)
			{
				isLine = false;
			}
		}
	}
	if (isLine) return TArray<FSpanTreeNode*>(); //不能一字长蛇，即，根节点必须至少三个孩子，或者其他任一节点必须至少两个孩子：这种情况必须重新生成树

	return tree;
}

void Architect::ReFlow(TArray<FSpanTreeNode*> tree, int minDistance, int maxDistance)
{
	reflowCount++;
	failed = false;

	// 用固体边缘初始化stage，切其他的所有东西都是Open但可以填充
	for (auto pos : *(stage->Bounds()))
	{
		auto tile = stage->Get(&pos);
		tile->SetType(FTileType::unformed);
		tile->owner = nullptr;
	}

	auto bounds = stage->Bounds()->Trace();
	for (auto pos : bounds)
	{
		stage->Get(&pos)->SetType(FTileType::solid);
	}

	// for (auto pos : *(stage->Bounds()))
	// {
	// 	auto tileType = stage->Get(&pos).type;
	// 	
	// 	UE_LOG(LogTD, Error, TEXT("TileType: %s"), *tileType->name);
	// }
	//
	// return;
	
	UE_LOG(LogTD, Error, TEXT("重新绘制"));
	//rootNode
	auto middle = new FVec(stage->Width() / 2, stage->Height() / 2);
	auto startTile = stage->Get(middle);
	auto rootNode = tree[0];
	rootNode->SelfContext->SettedPos = *middle;
	startTile->SetType(FTileType::open);
	startTile->owner = rootNode;
	reachability->ClearDistance(true);
	reachability->SetDistance(*middle, 0);  // 重置起始点

	TArray<FVec> *arr = new TArray<FVec>();
	arr->Emplace(*middle);
	reachability->Process(arr); // 重新设置距离

	// 根据树节点设置房间和距离
	for (auto treeNode : tree)
	{
		treeNode->Weight = Rng::rng()->Range(minDistance, maxDistance);
		treeNode->SelfContext->FlowedPoses.Empty();

		if(treeNode->IsRoot())
		{
			rootNode->SelfContext->FlowedPoses.Add(*middle);
			continue;;
		}

		FlowToTarget(treeNode);

		if(failed) break;
	}

	if(failed)
	{
		UE_LOG(LogTD, Error, TEXT("Flow失败，重新开始"));
	}
	else
	{
		UE_LOG(LogTD, Error, TEXT("Flow成功"));
	}
}

void Architect::FlowToTarget(FSpanTreeNode* endNode)
{
	auto parentTilePos = endNode->ParentNode->SelfContext->SettedPos;
	int targetDepth = endNode->Weight;
	reachability->ClearDistance();
	reachability->SetDistance(parentTilePos, 0);	//重置起始点

	TArray<FVec> *arr = new TArray<FVec>();
	arr->Emplace(parentTilePos);
	reachability->Process(arr);

	//todo：有可能永远卡住了；避免死循环
	auto startTilePos = parentTilePos;   //起点
	while (true)
	{
		startTilePos = FlowOnce(startTilePos, targetDepth, endNode);
		if (failed) break;
		if (startTilePos == FVec::DefaultVec) break;	// 到达终点
	}
}

FVec Architect::FlowOnce(FVec startTlPos, int targetDepth, FSpanTreeNode* endNode)
{
	auto parentDepth = reachability->Distances().Get(&startTlPos);
	auto neighbor = startTlPos.cardinalNeighbors();

	Rng::rng()->Shuffle(neighbor);

	for (auto here : neighbor)
	{
		if(!stage->Bounds()->Contains(here)) continue;	// 越过矩形区域
		if(reachability->Distances().Get(&here) != (parentDepth + 1)) continue;	// 非直系亲属
		auto tile = stage->Get(&here);

		// 可以行走 到达终点
		if(targetDepth == (parentDepth + 1))
		{
			endNode->SelfContext->FlowedPoses.Add(here); // 领土
			endNode->SelfContext->SettedPos = here;	//领土的尽头
			tile->type = FTileType::solidWet;
			tile->owner = endNode;
			return FVec::DefaultVec;
		}
		// 未到达终点
		else
		{
			endNode->SelfContext->FlowedPoses.Add(here); // 领土
			tile->type = FTileType::solid;
			tile->owner = endNode;
			return here;
		}
	}

	UE_LOG(LogTD, Error, TEXT("出问题了：当前位置：%d,%d"), startTlPos.x, startTlPos.y);
	this->failed = true;
	return FVec::DefaultVec; 
}
